//测试-二叉搜索树
//编译：g++ TestBinarySearchTree.cpp ../../*/*/BinarySearchTree.hpp -o test
#ifndef __TESTBINARYSEARCHTREE__CPP
#define __TESTBINARYSEARCHTREE__CPP

#include<iostream>
#include"../../DataStructure/Tree/BinarySearchTree.hpp"

using namespace std;
using namespace NgSiuKei;

int main(void) {
    binary_tree_node<char> *tree1 = createTree('1', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *tree2 = createTree('2', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *tree3 = createTree('3', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *tree4 = createTree('4', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *tree5 = createTree('5', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *tree6 = createTree('6', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);

    //前序：1 2 4 3 5 6
    //中序：4 2 1 5 3 6
    //后序：4 2 5 6 3 1
    //层序：1 2 3 4 5 6
    insertLeftSubTree(tree1, tree2);
    insertRightSubTree(tree1, tree3);
    insertLeftSubTree(tree2, tree4);
    insertLeftSubTree(tree3, tree5);
    insertRightSubTree(tree3, tree6);

    U_L_L num = getTreeNodeNum(tree1);
    U_L_L height = getTreeHeight(tree1);
    cout << "num = " << num << endl;
    cout << "height = " << height << endl;

    char *preArray = orderTree(tree1, ORDER_TYPE_PRE);
    char *inArray = orderTree(tree1, ORDER_TYPE_IN);
    char *postArray = orderTree(tree1, ORDER_TYPE_POST);
    char *levelArray = orderTree(tree1, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;

    delete preArray;
    delete inArray;
    delete postArray;
    delete levelArray;

    cout << "————构建二叉搜索树————" << endl;
    //前序：3 2 1 5 4 6
    //中序：1 2 3 4 5 6
    //后序：1 2 4 6 5 3
    //层序：3 2 5 1 4 6
    binary_tree_node<char> *binarySearchTree = createBinarySearchTree(tree1);
    if(isBST(binarySearchTree)) {
        cout << "构建成功" << endl;
    }

    preArray = orderTree(binarySearchTree, ORDER_TYPE_PRE);
    inArray = orderTree(binarySearchTree, ORDER_TYPE_IN);
    postArray = orderTree(binarySearchTree, ORDER_TYPE_POST);
    levelArray = orderTree(binarySearchTree, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;

    if(findVal(binarySearchTree, '5')) {
        cout << "找得到5" << endl;
    }
    if(!findVal(binarySearchTree, '8')) {
        cout << "找不到8" << endl;
        insertValToBinarySearchTree(binarySearchTree, '8');
        if(findVal(binarySearchTree, '8')) {
            cout << "找得到8" << endl;
        }
    }
    cout << "最小值 = " << getMinVal(binarySearchTree) << endl;
    cout << "最大值 = " << getMaxVal(binarySearchTree) << endl;
    cout << "删除前num = " << getTreeNodeNum(binarySearchTree) << endl;
    deleteValFromBinarySearchTree(binarySearchTree, '5');
    cout << "删除后num = " << getTreeNodeNum(binarySearchTree) << endl;


    delete preArray;
    delete inArray;
    delete postArray;
    delete levelArray;

    levelArray = orderTree(binarySearchTree, ORDER_TYPE_LEVEL);
    cout << "层序 = [ ";
    for(U_L_L i=0; i<getTreeNodeNum(binarySearchTree); ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;
    delete levelArray;

    cout << "普通二叉树->二叉搜索树" << endl;
    convertToBinarySearchTree(tree1);
    levelArray = orderTree(tree1, ORDER_TYPE_LEVEL);
    cout << "层序 = [ ";
    for(U_L_L i=0; i<getTreeNodeNum(binarySearchTree); ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;
    delete levelArray;
    if(isBST(tree1)) {
        cout << "tree1已经是个BST了" << endl;
    }

    clearTree(tree1);
    clearTree(binarySearchTree);

    return 0;
}

#endif